package A一周刷爆LeetCode.B基础提升.B并查集;

/**
 * @author wei.zhao
 * @description: 岛问题
 * @date 2022年06月23日 11:55
 */
public class Code01_Islands {

    public static int countIslands(int[][] arr) {
        int result = 0;
        int row = arr.length;
        int col = arr[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == 1) {
                    result++;
                    infect(arr, i, j, row, col);
                }
            }
        }
        return result;
    }

    private static void infect(int[][] arr, int i, int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col || arr[i][j] != 1) {
            return;
        }
        arr[i][j] = -1;
        infect(arr, i - 1, j, row, col);
        infect(arr, i, j - 1, row, col);
        infect(arr, i + 1, j, row, col);
        infect(arr, i, j + 1, row, col);
    }

    public static void main(String[] args) {
        int[][] m1 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0}
        };
        System.out.println(countIslands(m1));

        int[][] m2 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0}
        };
        System.out.println(countIslands(m2));
    }

}
